We study the problem of maximising the lifetime of a sensor\udnetwork for fault-tolerant target coverage in a setting\udwith composite events. Here, a composite event is the simultaneous\udoccurrence of a combination of atomic events,\udsuch as the detection of smoke and high temperature. We\udare given sensor nodes that have an initial battery level\udand can monitor certain event types, and a set of points\udat which composite events need to be detected. The points\udand sensor nodes are located in the Euclidean plane, and all\udnodes have the same sensing radius. The goal is to compute\uda longest activity schedule with the property that at any\udpoint in time, each event point is monitored by at least two\udactive sensor nodes. We present a (6 + ε)-approximation\udalgorithm for this problem by devising an approximation\udalgorithm with the same ratio for the dual problem of minimising\udthe weight of a fault-tolerant sensor cover and applying\udthe Garg-Könemann algorithm. Our algorithm for the\udminimum-weight fault-tolerant sensor cover problem generalises\udprevious approximation algorithms for geometric set\udcover with weighted unit disks and is obtained by enumerating\udproperties of the optimal solution that guide a dynamic\udprogramming approach.
展开▼
